home *** CD-ROM | disk | FTP | other *** search
/ Scene Storm / Scene Storm - Volume 1.iso / coding / c / lha_axeman / maketree.c < prev    next >
C/C++ Source or Header  |  1995-09-01  |  3KB  |  140 lines
  1. /***********************************************************
  2.     maketree.c -- make Huffman tree
  3. ***********************************************************/
  4. #include "slidehuf.h"
  5.  
  6. static short n, heapsize, heap[NC + 1];
  7. static unsigned short *freq, *sort;
  8. static unsigned char *len;
  9. static unsigned short len_cnt[17];
  10.  
  11. void make_code(n, len, code)
  12. int n;
  13. unsigned char len[];
  14. unsigned short code[];
  15. {
  16.     unsigned short weight[17]; /* 0x10000ul >> bitlen */
  17.     unsigned short start[17];  /* start code */
  18.     unsigned short j, k;
  19.     int i;
  20.  
  21.     j = 0; k = 1 << (16 - 1);
  22.     for (i = 1; i <= 16; i++) {
  23.         start[i] = j;
  24.         j += (weight[i] = k) * len_cnt[i];
  25.         k >>= 1;
  26.     }
  27.     for (i = 0; i < n; i++) {
  28.         j = len[i];
  29.         code[i] = start[j];
  30.         start[j] += weight[j];
  31.     }
  32. }
  33.  
  34. static void count_len(i)  /* call with i = root */
  35. int i;
  36. {
  37.     static unsigned char depth = 0;
  38.  
  39.     if (i < n) len_cnt[depth < 16 ? depth : 16]++;
  40.     else {
  41.         depth++;
  42.         count_len(left [i]);
  43.         count_len(right[i]);
  44.         depth--;
  45.     }
  46. }
  47.  
  48. static void make_len(root)
  49. int root;
  50. {
  51.   int i, k;
  52.   unsigned int cum;
  53.  
  54.   for (i = 0; i <= 16; i++) len_cnt[i] = 0;
  55.   count_len(root);
  56.   cum = 0;
  57.   for (i = 16; i > 0; i--) {
  58.     cum += len_cnt[i] << (16 - i);
  59.   }
  60. #if (UINT_MAX != 0xffff)
  61.   cum &= 0xffff;
  62. #endif
  63. /* adjust len */
  64.     if (cum) {
  65.       fprintf(stderr, "17");
  66.       len_cnt[16] -= cum;        /* always len_cnt[16] > cum */
  67.       do {
  68.     for (i = 15; i > 0; i--) {
  69.       if (len_cnt[i]) {
  70.         len_cnt[i]--; len_cnt[i + 1] += 2; break;
  71.       }
  72.     }
  73.       } while (--cum);
  74.     }
  75. /* make len */
  76.   for (i = 16; i > 0; i--) {
  77.     k = len_cnt[i];
  78.     while (k > 0) {
  79.       len[*sort++] = i;
  80.       k--;
  81.     }
  82.   }
  83. }
  84.  
  85. static void downheap(i)
  86.     /* priority queue; send i-th entry down heap */
  87. int i;
  88. {
  89.   short j, k;
  90.  
  91.   k = heap[i];
  92.   while ((j = 2 * i) <= heapsize) {
  93.     if (j < heapsize && freq[heap[j]] > freq[heap[j + 1]])
  94.       j++;
  95.     if (freq[k] <= freq[heap[j]]) break;
  96.     heap[i] = heap[j];  i = j;
  97.   }
  98.   heap[i] = k;
  99. }
  100.  
  101. short make_tree(nparm, freqparm, lenparm, codeparm)
  102.     /* make tree, calculate len[], return root */
  103. int nparm;
  104. unsigned short freqparm[];
  105. unsigned char lenparm[];
  106. unsigned short codeparm[];
  107. {
  108.     short i, j, k, avail;
  109.  
  110.     n = nparm;  freq = freqparm;  len = lenparm;
  111.     avail = n;  heapsize = 0;  heap[1] = 0;
  112.     for (i = 0; i < n; i++) {
  113.         len[i] = 0;
  114.         if (freq[i]) heap[++heapsize] = i;
  115.     }
  116.     if (heapsize < 2) {
  117.         codeparm[heap[1]] = 0;
  118.         return heap[1];
  119.     }
  120.     for (i = heapsize / 2; i >= 1; i--)
  121.         downheap(i);  /* make priority queue */
  122.     sort = codeparm;
  123.     do {  /* while queue has at least two entries */
  124.         i = heap[1];  /* take out least-freq entry */
  125.         if (i < n) *sort++ = i;
  126.         heap[1] = heap[heapsize--];
  127.         downheap(1);
  128.         j = heap[1];  /* next least-freq entry */
  129.         if (j < n) *sort++ = j;
  130.         k = avail++;  /* generate new node */
  131.         freq[k] = freq[i] + freq[j];
  132.         heap[1] = k;  downheap(1);  /* put into queue */
  133.         left[k] = i;  right[k] = j;
  134.     } while (heapsize > 1);
  135.     sort = codeparm;
  136.     make_len(k);
  137.     make_code(nparm, lenparm, codeparm);
  138.     return k;  /* return root */
  139. }
  140.